% Ejercicio "Cadenas de paréntesis"
\subsection*{\fbox{\theejercicio} - Cadenas de par\'entesis}

Consideremos qel lenguaje formando por cadenas balanceadas y par\'entesis () y par\'entesis ``\'angulo'' $<>$. Ejemplos de cadenas v\'alidas son:

\begin{verbatim}
(<>(()))
((<()>))()
( <> (<<( )>>)(()) ) < () (<>) >
\end{verbatim}

No son cadenas v\'alidas, por ejemplo:

\begin{verbatim}
((<))
(<>)(<()>))
(<(>))
\end{verbatim}

En esta \'ultima, aunque hay el mismo n\'umero de par\'entesis de apertura que de cierre, tampoco es v\'alida,
pues el s\'{\i}mbolo ``$>$'' aparece antes de que se hayan cerrado todos los par\'entesis abiertos que aparecen
despu\'es del par\'entesis de apertura que es pareja con \'el: $<(>$

\begin{enumerate}[1)]
\item Escribir una gram\'atica con un solo elemento no terminal para este lenguaje.
\item Construir las tablas SLR(1) para esta gram\'atica.
\item ?`Es SLR(1)?. Si lo es, explica por qu\'e, en caso de que no lo sea, comenta c\'omo podr\'{\i}a modificarse la gram\'atica para que lo fuera.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\begin{center}
\begin{tabular}{|llcl|} \hline
        &          &               &                         \\
{\tt 0} & {\em S'} & $\rightarrow$ & {\em S} {\bf \$}        \\
{\tt 1} & {\em S}  & $\rightarrow$ & {\em S S}               \\
{\tt 2} &          & $|$           & {\bf (} {\em S} {\bf )} \\
{\tt 3} &          & $|$           & {\bf ( )}               \\
{\tt 4} &          & $|$           & $<$ {\em S} $>$         \\
{\tt 5} &          & $|$           & {\em S}                 \\
        &          &               &                         \\ \hline
\end{tabular}
\end{center}

Apartado 2)

\begin{center}
\begin{tabular}{|l|cccccc|} \hline
         & {\em S} & {\bf (}  & {\bf )} & $<$      & $>$   & {\bf \$} \\ \hline
{\tt 0}  & 1       & D2       &         & D3       &       &          \\
{\tt 1}  & 4       & D5       &         & D3       &       & A        \\
{\tt 2}  & 6       & D5       & D7      & D3       &       &          \\
{\tt 3}  & 8       & D5/$R_1$ &         & D3       & D9    &          \\
{\tt 4}  & 4       & D5       & $R_1$   & D3/$R_1$ &       & $R_1$    \\
{\tt 5}  & 6       & D5       & D7      & D3       & $R_1$ &          \\
{\tt 6}  & 4       & $R_3$    & D10     & D3       &       &          \\
{\tt 7}  &         & D5       & $R_3$   & $R_3$    & $R_3$ & $R_3$    \\
{\tt 8}  & 4       & $R_5$    &         & D3       & D11   &          \\
{\tt 9}  &         & $R_2$    & $R_5$   & $R_5$    & $R_5$ & $R_5$    \\
{\tt 10} &         & $R_2$    & $R_2$   & $R_2$    & $R_2$ & $R_2$    \\
{\tt 11} &         & $R_4$    & $R_4$   & $R_4$    & $R_4$ & $R_4$    \\ \hline
\end{tabular}
\end{center}

Apartado 3)

\medskip

No es SLR(1), hay conflictos Reducir/Desplazar. Esto es debido a que la gram\'atica es ambigua. Se podr\'{\i}a resolver modificando la gram\'atica a \'esta:

\begin{center}
\begin{tabular}{|llcl|} \hline
        &          &               &                         \\
{\tt 0} & {\em S'} & $\rightarrow$ & {\em S} {\bf \$}        \\
{\tt 1} & {\em S}  & $\rightarrow$ & {\em S T}               \\
{\tt 2} &          & $|$           & {\em T}                 \\
{\tt 3} & {\em T}  & $\rightarrow$ & {\bf (} {\em S} {\bf )} \\
{\tt 4} &          & $|$           & {\bf ( )}               \\
{\tt 5} &          & $|$           & $<$ {\em S} $>$         \\
{\tt 6} &          & $|$           & $< >$                   \\ \hline
\end{tabular}
\end{center}